home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_12 / engbert / list.c < prev    next >
Text File  |  1993-05-11  |  3KB  |  158 lines
  1. /*                               LIST.C
  2. **
  3. ** This file builds/maintains the "Huffman list".
  4. ** The first element in the list holds the most
  5. ** frequent character. Other characters follow
  6. ** in order of decreasing frequency.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <conio.h>
  12. #include <ctype.h>
  13. #include "config.h"
  14. #include "proto.h"  /* prototypes */
  15.  
  16. #define BYTE_RANGE              256
  17. signed int user_byte;  /* global shared with COMP.C */
  18.  
  19.  
  20. struct list {
  21.     unsigned char character;
  22.     unsigned int count;
  23. };
  24. static struct list list[BYTE_RANGE+1];
  25.  
  26.  
  27. /* set list back to all zeros, for multiple files!*/
  28.  
  29. init_list() {
  30. int i;
  31.     for (i=0;i< BYTE_RANGE;i++) {
  32.         list[i].character = 0;
  33.         list[i].count = 0;
  34.     }
  35. }
  36.  
  37. #ifdef COMPRESS
  38.  
  39. void encode_byte(unsigned int start,
  40.      unsigned int list_count, unsigned int count){
  41.  
  42. unsigned int i,j,number,maximum;
  43. unsigned char found;
  44.  
  45.     found = 0;
  46.  
  47.     if (list_count ==1) {
  48.         if (!list[start].count) write_byte(user_byte);
  49.         else;
  50.         return;  /* if there is only 1 element left*/
  51.     }
  52.  
  53.     /* is character in first half? : */
  54.  
  55.     maximum = list_count/2;
  56.     number = 0;
  57.     j = 0; /*running total of [].count*/
  58.     i = start;
  59.     do {
  60.         j += list[i].count;
  61.         if (list[i].character == user_byte) {
  62.             found++;
  63.             write_bit(0);
  64.         } else;
  65.         i++;
  66.         number++;
  67.     } while (  j < (count / 2) && number < maximum );
  68.  
  69.     if (found) encode_byte(start,number,j);
  70.     /* character was in first half*/
  71.     else {
  72.         /* character was in second half: */
  73.         write_bit(1);
  74.         encode_byte(i,list_count-number, count -j);
  75.     }
  76. }
  77.  
  78. #else COMPRESS
  79.  
  80. extern signed int bit;  /*global shared with COMP.C */
  81. void decode_byte(unsigned int start,
  82.      unsigned int list_count, unsigned int count){
  83.  
  84. unsigned int i,j,number,maximum;
  85. int c;
  86.  
  87.     /* is char in first half? : */
  88.     if (list_count == 1) {
  89.         if (!list[start].count) {
  90.             /* Here we just positioned at the empty
  91.             leaf, so pick up 8 bits as literal ASCII:*/
  92.             user_byte = read_byte(bit);
  93.             /* bit is the first bit of new user_byte */
  94.             bit= read_bit();
  95.         } else user_byte = list[start].character;
  96.         return;    /* if there is only 1 element left*/
  97.     }
  98.     maximum = list_count/2;
  99.     number = 0;
  100.     j = 0; /*running total of [].count*/
  101.     i = start;
  102.     do {
  103.         j += list[i].count;
  104.         i++;
  105.         number++;
  106.     } while (  j < (count / 2) && number < maximum ) ;
  107.  
  108.     /* read first/second half of list as required: */
  109.     if ( !bit) {
  110.         bit = read_bit();
  111.         decode_byte(start, number,j);
  112.     }
  113.     else {
  114.         bit = read_bit();
  115.         decode_byte(i, list_count-number, count -j);
  116.     }
  117. }
  118.  
  119. #endif
  120.  
  121.  
  122. void update_list( unsigned int *byte_count,
  123.      unsigned int *character_count) {
  124. unsigned int i;
  125. unsigned int hold_i;
  126. unsigned int count;
  127.  
  128.     (*byte_count) ++;
  129.  
  130.     hold_i = i = 0;
  131.     while (count = list[i].count) {
  132.         do {
  133.             if (list[i].character == user_byte) {
  134.                 if (  hold_i != i) {
  135.                     list[i].character = list[hold_i].character;
  136.                     list[hold_i].character = user_byte;
  137.                     list[hold_i].count++;
  138.                 } else {
  139.                     list[i].count++;
  140.                 }
  141.                 return;
  142.             } else i++;
  143.         } while ( list[i].count == count);
  144.         hold_i = i;
  145.         /* hold_i is first char with this count */
  146.     }
  147.  
  148.     /* Add new character to list: */
  149.  
  150.     (*character_count)++;
  151.     list[i].character = user_byte;
  152.     list[i].count++;
  153. } /*update_list */
  154.  
  155.  
  156.  
  157.  
  158.